package mo.offer_special;

import java.util.Stack;

public class L039 {

    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int area = 0;
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                area = Math.max(area, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            area = Math.max(area, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return area;
    }


    public static void main(String[] args) {
        L039 test = new L039();
        System.out.println(test.largestRectangleArea(new int[]{1, 1}));
    }

}
